class Solution(object):
    def combine(self, n, k):
        """
https://leetcode.cn/problems/combinations/description/

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """

        if k == 0:
            return [[]]
        if k == n:
            return [[i for i in range(1, n + 1)]]

        includes = self.combine(n - 1, k - 1)
        non_includes = self.combine(n - 1, k)

        for it in includes:
            it.append(n)

        return includes + non_includes